#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int maxn = 7e5 + 10;
int h[maxn];
int stk[maxn];
int hl[maxn], hr[maxn];
int top;
int n;
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	
	// 先处理左边的
	for(int i=1;i<=n;i++){
		while(top&&h[stk[top]]<=h[i]){ // 需要弹出的情况
			top--;
		}
		hl[i]=top?stk[top]:-1;
		stk[++top]=i; // 注意这里面 单调栈存储的是 下标
	}
	
	// 再处理右边的
	top=0;
	for(int i=n;i>=1;i--){
		while(top&&h[stk[top]]<=h[i]){ // 需要弹出的情况
			top--;
		}
		hr[i]=top?stk[top]:-1;
		stk[++top]=i;
	}
	
	for(int i=1;i<=n;i++){
		cout<<hl[i]<<' ';
	}
	cout<<'\n';
	
	for(int i=1;i<=n;i++){
		cout<<hr[i]<<' ';
	}
	cout<<'\n';
}

signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}
